#include <stdio.h>
/*
    插入排序 
    1.手上初始有一张牌 -- a[0]
    2.摸一张牌 --a[1]
    3.比较a[1]和a[0]
    4.若a[0]>a[1] --a[0]往后挪出一个位置
    5.a[0]填坑

    更普遍的
    1.当前 前p-1个元素排序已经排好序了
    2.插入一个元素a[p]
    3.temp=a[p]
    4.i=p-1 比较a[i]与temp大小
    5.a[i]>temp a[i]往后挪 a[i+1]=a[i]; 
    6.a[i]<temp temp放在这个i+1这个坑上
*/
void insert_sort(int a[], int n)
{
    int i;
    for (int p = 1; p < n; p++)
    {
        int temp = a[p];
        for (i = p - 1; i >= 0 && a[i] > temp; i--)
            a[i + 1] = a[i];
        a[i + 1] = temp;
    }
}

void main()
{
    int a[] = {4, 3, 8, 2, 7, 11, 6, 1, 0, 15};
    insert_sort(a, 10);
    for (int i = 0; i < 10; i++)
        printf("%3d", a[i]);
}